home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / pcr / pcr4_4.lha / DIST / gc / INCLUDE / xr / GCPrivate.h < prev    next >
C/C++ Source or Header  |  1992-04-16  |  42KB  |  1,182 lines
  1. /* begincopyright
  2.   Copyright (c) 1988-1991 Xerox Corporation. All rights reserved.
  3.   Use and copying of this software and preparation of derivative works based
  4.   upon this software are permitted. Any distribution of this software or
  5.   derivative works must comply with all applicable United States export
  6.   control laws. This software is made available AS IS, and Xerox Corporation
  7.   makes no warranty about the software, its performance or its conformity to
  8.   any specification. Any person obtaining a copy of this software is requested
  9.   to send their name and post office or electronic mail address to:
  10.     PCR Coordinator
  11.     Xerox PARC
  12.     3333 Coyote Hill Rd.
  13.     Palo Alto, CA 94304
  14.     
  15.   Parts of this software were derived from code bearing the copyright notice:
  16.   
  17.   Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
  18.   This material may be freely distributed, provided this notice is retained.
  19.   This material is provided as is, with no warranty expressed or implied.
  20.   Use at your own risk.
  21.   
  22.   endcopyright */
  23.   
  24. /* Machine specific parts contributed by various other people.        */
  25. /* This version assumes a table of heap pages is maintained.          */
  26.  
  27. /*
  28.  * Derived from both the  Boehm-Demers collector, and the initial PCR
  29.  * collector built by Weiser, Hauser et al..
  30.  * Boehm, May 29, 1991 1:08:24 pm PDT
  31.  */
  32.  
  33. #ifndef _XR_GCPrivate_
  34. #define _XR_GCPrivate_ 1
  35.  
  36. # include "xr/GC.h"
  37.  
  38. # include "xr/ThreadsBackdoor.h"
  39.  
  40. typedef unsigned long word;  
  41.  
  42.  
  43. /*********************************/
  44. /*                               */
  45. /* Definitions for conservative  */
  46. /* collector                     */
  47. /*                               */
  48. /*********************************/
  49.  
  50. /*********************************/
  51. /*                               */
  52. /* Easily changeable parameters  */
  53. /*                               */
  54. /*********************************/
  55.  
  56. # if defined(sun) && defined(mc68000)
  57. #    define M68K_SUN
  58. #    define mach_type_known
  59. # endif
  60. # if defined(hp9000s300)
  61. #    define M68K_HP
  62. #    define mach_type_known
  63. # endif
  64. # if defined(vax)
  65. #    define VAX
  66. #    define mach_type_known
  67. # endif
  68. # if defined(mips)
  69. #    define MIPS
  70. #    define mach_type_known
  71. # endif
  72. # if defined(sequent) && defined(i386)
  73. #    define I386
  74. #    define mach_type_known
  75. # endif
  76. # if defined(ibm032)
  77. #   define RT
  78. #   define mach_type_known
  79. # endif
  80. # if defined(sun) && defined(sparc)
  81. #   define SPARC
  82. #   define mach_type_known
  83. # endif
  84. # if defined(_IBMR2)
  85. #   define IBMRS6000
  86. #   define mach_type_known
  87. # endif
  88.  
  89.  
  90. /* Feel free to add more clauses here */
  91.  
  92. /* Or manually define the machine type here: */
  93. # ifndef mach_type_known
  94. #   define M68K_SUN /* Guess "Sun" */
  95.             /* Mapping is: M68K_SUN   ==> Sun3,                */
  96.             /*             M68K_HP    ==> HP9000/300,          */
  97.             /*             I386       ==> Sequent Symmetry,    */
  98.                     /*             NS32K      ==> Encore Multimax,     */
  99.                     /*             MIPS       ==> R2000 or R3000       */
  100. # endif
  101.  
  102. #define GATHERSTATS /* Compute garbage collection statistics not necessary */
  103.             /* for normal GC operation.                   */
  104.             
  105. #define PRINTSTATS
  106.             /* Print garbage collection statistics                 */
  107.             /* For less verbose output, undefine in reclaim.c      */
  108.  
  109. #define PRINTTIMES
  110.             /* Print the amount of time consumed by each garbage   */
  111.             /* collection.                                         */
  112.  
  113. #define PRINTBLOCKS /* Print object sizes associated with heap blocks,     */
  114.             /* whether the objects are atomic or composite, and    */
  115.             /* whether or not the block was found to be empty      */
  116.             /* during the reclaim phase.  Typically generates      */
  117.             /* about one screenful per garbage collection.         */
  118. #undef PRINTBLOCKS
  119.  
  120. #define REPORT_FAILURE   /* Print values that looked "almost" like pointers */
  121. #undef REPORT_FAILURE
  122.  
  123.  
  124. #ifdef SILENT
  125. #  ifdef PRINTSTATS
  126. #    undef PRINTSTATS
  127. #  endif
  128. #  ifdef PRINTTIMES
  129. #    undef PRINTTIMES
  130. #  endif
  131. #  ifdef PRINTNBLOCKS
  132. #    undef PRINTNBLOCKS
  133. #  endif
  134. #endif
  135.  
  136. #if defined(PRINTSTATS) && !defined(GATHERSTATS)
  137. #  define GATHERSTATS
  138. #endif
  139.  
  140.  
  141. #define MAP_SIZE 24576  /* total data size < MAP_SIZE * HBLKSIZE = 96 Meg  */
  142.  
  143. #define INTERIOR_POINTERS
  144.             /* Follow pointers to the interior of an object.      */
  145.             /* Substantially increases the probability of         */
  146.             /* unnnecessary space retention.  May be necessary    */
  147.             /* with gcc -O or other C compilers that may clobber  */
  148.             /* values of dead variables prematurely.  Pcc         */
  149.             /* derived compilers appear to pose no such problems. */
  150.             /* Empirical evidence suggests that this is probably  */
  151.             /* still OK for most purposes, so long as pointers    */
  152.             /* are known to be 32 bit aligned.  The combination   */
  153.             /* of INTERIOR_POINTERS and UNALIGNED (e.g. on a      */
  154.             /* Sun 3 with the standard compiler) causes easily    */
  155.             /* observable spurious retention and performance      */
  156.             /* degradation.                                       */
  157.  
  158. #define RESTRICTED_INTERIOR_POINTERS
  159.             /* Accept pointers into the middle of objects only   */
  160.             /* if the displacement from the beginning of the     */
  161.             /* object is one previously registered with          */
  162.             /* GC_register_displacement.             */
  163.             /* Registered displacements must be expressible      */
  164.             /* in words, and must be < MAX_OFFSET         */
  165.             
  166. #define INTERIOR_STACK_POINTERS
  167.             /* Accept pointers into the middle of objects    */
  168.             /* from the stack area even if they are not        */
  169.             /* otherwise accepted.  If this is defined, then    */
  170.             /* RESTRICTED_INTERIOR_POINTERS applies only to     */
  171.             /* the heap and to static data areas.        */
  172.             
  173. #define BLACK_LIST
  174.             /* Maintain a list of pages that have known false    */
  175.             /* references to them, and should thus not contain    */
  176.             /* objects that may bin large amounts of memory.    */
  177.  
  178. #ifdef SPARC
  179.     /* On a SPARC, this appears to result in lots of false hits, since  */
  180.     /* the architecture and compilers are sloppy about stack space         */
  181.     /* usage.                                                              */
  182. #  undef INTERIOR_STACK_POINTERS
  183. #endif
  184.             
  185. #ifdef RESTRICTED_INTERIOR_POINTERS
  186. #   define MAX_OFFSET 4096
  187. #   define MAP_CACHE_SZ 20  /* Maps of block layout are built for         */
  188.                 /* MAP_CACHE_SZ different allocation sizes      */
  189.                 /* less than MAXOBJSZ.                */
  190. #endif    
  191.  
  192. #ifdef BLACK_LIST
  193. # ifdef INTERIOR_STACK_POINTERS
  194.    --> not implemented correctly
  195. # endif
  196. # if defined INTERIOR_POINTERS && !defined(RESTRICTED_INTERIOR_POINTERS)
  197.    --> not implemented correctly
  198. # endif
  199. #endif
  200.  
  201. #define SEPARATE_HEADERS
  202.             /* Keep mark bits and other information associated   */
  203.             /* with heap blocks separate from the heap blocks    */
  204.             /* themselves.  Especially in combination with       */
  205.             /* DIRTY_BITS, this can significantly reduce        */
  206.             /* page faults for large address spaces.  In the     */
  207.             /* case of non-32-bit aligned pointers, it still     */
  208.             /* makes sense to discard the beginning of blocks    */
  209.             /* however, since there are otherwise too many bogus */
  210.             /* references to these locations.                    */
  211.  
  212.  
  213. #ifdef SEPARATE_HEADERS
  214. #   define DISCARD_WORDS 16  /* Discard this many words at the beginning   */
  215.                  /* of each block, if pointers are not aligned */
  216.             /* The definition of quicktest below assumes a value   */
  217.             /* of at least 8.                                      */
  218. #   define ALIGNED_DISCARD_WORDS 0 /* Analogous value if pointers are  */
  219.                    /* aligned.  Less critical, since   */
  220.                    /* bogus pointers to the beginning  */
  221.                    /* of a block are less likely.      */
  222. #endif
  223.  
  224. #ifdef SPARC
  225. #   define ALIGN_DOUBLE  /* Align objects of size > 1 word on 2 word   */
  226.              /* boundaries.  Wasteful of memory, but       */  
  227.              /* apparently required by SPARC architecture. */
  228. #endif
  229.  
  230. #define FREE_MEM_RATIO 4
  231.             /* Initial value of GC_free_mem_ratio.  Should  */
  232.             /* be >= 1.                    */
  233. #define MAX_HINCR 1024 /* Maximum number of heap blocks by which to expand  */
  234.              /* the heap at once (unless forced).                   */
  235. #define MIN_HINCR 256    /* Minimum number of heap blocks by which to expand  */
  236.             /* the heap at once.                     */
  237.  
  238. #define DIRTY_BITS
  239.             /* Virtual dirty bits are available, enabling the   */
  240.             /* following strategy (unless GC_mode dictates    */
  241.             /* otherwise):                    */
  242.             /* Perform frequent "ephemeral" collections to      */
  243.             /* reduce the frequency of full collections.        */
  244.             /* Clear mark bits only for full garbage            */
  245.             /* collection.  For the other collections, leave    */
  246.             /* mark bits set from the preceding collection,     */
  247.             /* and treat marked objects on dirty pages as roots.*/
  248.             /* Try to reclaim objects only on dirty pages.      */
  249.             /* In order to keep as many pages as possible clean */
  250.             /* we do not allocate objects that are expected to  */
  251.             /* be shortlived on pages that satisfy the TOO_FULL */
  252.             /* criterion.                                       */
  253. # ifdef IBMRS6000
  254.     /* We don't have virtual dirty bits on an RS/6000 yet */
  255. #   undef DIRTY_BITS
  256. # endif
  257.  
  258. #  define TENURE(empty_words) \
  259.             (BYTES_TO_WORDS(HBLKSIZE) > ((empty_words) << 2))
  260.             /* At most 1/4 can still be allocated */
  261.             /* Criterion for tenuring a heap block.  If a heap  */
  262.             /* block is sufficiently full, we stop allocating   */
  263.             /* from it to keep it clean and to improve        */
  264.             /* allocation locality.                            */  
  265.             /* empty_words are the number of remaining words in */
  266.             /* the heap block that can be allocated.            */
  267.             
  268. # define MIN_COMPOSITE_IN_USE 500000
  269.             /* Minimum on accessible composite words used in */
  270.             /* garbage collection decisions.  Large values   */
  271.             /* inhibit frequent collections during startup   */
  272.             /* but generate longer pauses.                   */
  273.  
  274. #define FULL_GC_ALLOCS 0     /* Invoke the full collector after this many  */
  275.                     /* words are allocated.  Note that allocation */
  276.                     /* count  is reset to 0 after any kind of     */
  277.                     /* collection.                      */
  278.                     /* This is only a default value.          */
  279.                     /* 0 ==> collect only when full. A 0 value    */
  280.                     /* is highly recommended at the moment.       */   
  281.  
  282. #define MERGE_SIZES /* Round up some object sizes, so that fewer distinct */
  283.             /* free lists are actually maintained.  This applies  */
  284.             /* only to the top level routines in misc.c, not to   */
  285.             /* user generated code that calls allocobj and        */
  286.             /* allocaobj directly.                                */
  287.             /* Slows down average programs slightly.  May however */
  288.             /* substantially reduce fragmentation if allocation   */
  289.             /* request sizes are widely scattered.                */
  290.  
  291. /* ALIGN_DOUBLE requires MERGE_SIZES at present. */
  292. # if defined(ALIGN_DOUBLE) && !defined(MERGE_SIZES)
  293. #   define MERGE_SIZES
  294. # endif
  295.  
  296. /* RESTRICTED_INTERIOR_POINTERS requires INTERIOR_POINTERS */
  297. # if defined(RESTRICTED_INTERIOR_POINTERS) && !defined(INTERIOR_POINTERS)
  298. #   define INTERIOR_POINTERS
  299. # endif
  300.  
  301. #define VISUALIZE   /* Make calls to Mark Weiser's GC visualizer */
  302.  
  303. #undef VISUALIZE
  304.  
  305.  
  306. /* For PRINTTIMES to tell the truth, we need to know the value of HZ for
  307.    this system. */
  308.  
  309. #if defined(M68K_HP) || defined(M68K_SUN) || defined(SPARC)
  310. #  include <sys/param.h>
  311. #  define LOCAL_HZ HZ
  312. #else
  313. #  define LOCAL_HZ 60    /* Guess that we're in the U.S. */
  314. #endif
  315.  
  316. #ifdef M68K_SUN
  317. #  define UNALIGNED       /* Pointers are not longword aligned         */
  318. #  define ALIGNMENT   2   /* Pointers are aligned on 2 byte boundaries */
  319.               /* by the Sun C compiler.                    */
  320. #else
  321. #  ifdef VAX
  322. #    undef UNALIGNED      /* Pointers are longword aligned by 4.2 C compiler */
  323. #    define ALIGNMENT 4
  324. #  else
  325. #    ifdef RT
  326. #      undef UNALIGNED
  327. #      define ALIGNMENT 4
  328. #    else
  329. #      ifdef SPARC
  330. #        undef UNALIGNED
  331. #        define ALIGNMENT 4
  332. #      else
  333. #        ifdef I386
  334. #           undef UNALIGNED         /* Sequent compiler aligns pointers */
  335. #           define ALIGNMENT 4
  336. #        else
  337. #          ifdef NS32K
  338. #            undef UNALIGNED        /* Pointers are aligned on NS32K */
  339. #            define ALIGNMENT 4
  340. #          else
  341. #            ifdef MIPS
  342. #              undef UNALIGNED      /* MIPS hardware requires pointer */
  343.                     /* alignment                      */
  344. #              define ALIGNMENT 4
  345. #            else
  346. #              ifdef M68K_HP
  347. #                define UNALIGNED
  348. #                define ALIGNMENT 2 /* 2 byte alignment inside struct/union, */
  349.                     /* 4 bytes elsewhere */
  350. #              else
  351. #         ifdef IBMRS6000
  352. #           undef UNALIGNED
  353. #           define ALIGNMENT 4
  354. #         else
  355.             --> specify alignment <--
  356. #         endif
  357. #              endif
  358. #            endif
  359. #          endif
  360. #        endif
  361. #      endif
  362. #    endif
  363. #  endif
  364. #endif
  365.  
  366. # define GC_MULT 3         /* Don't collect if the fraction of   */
  367.                /* non-collectable memory in the heap */
  368.                /* exceeds GC_MUL/GC_DIV              */
  369. # define GC_DIV  4
  370.  
  371. # define NON_GC_HINCR MIN_HINCR
  372.                /* Heap increment if most of heap if collection */
  373.                /* was suppressed because most of heap is not   */
  374.                /* collectable                                  */
  375.  
  376. /*  heap address bounds.  These are extreme bounds used for sanity checks. */
  377. /*  HEAPLIM may have to be increased for machines with incredibly large    */
  378. /*  amounts of memory.                                                     */
  379.  
  380. #ifdef RT
  381. #   define HEAPSTART 0x10000000
  382. #   define HEAPLIM   0x1fff0000
  383. #else
  384. # if defined(M68K_SUN) || defined(M68K_HP)
  385. #   define HEAPSTART 0x00010000
  386. #   define HEAPLIM   0x04000000
  387. # else
  388. #   ifdef SPARC
  389. #       define HEAPSTART 0x00010000
  390. #       define HEAPLIM   0x10000000
  391. #   else
  392. #     ifdef VAX
  393. #       define HEAPSTART 0x400
  394. #       define HEAPLIM   0x10000000
  395. #     else
  396. #       ifdef I386
  397. #         define HEAPSTART 0x1000
  398. #         define HEAPLIM 0x10000000
  399. #       else
  400. #         ifdef NS32K
  401. #           define HEAPSTART 0x2000
  402. #           define HEAPLIM   0x10000000
  403. #         else
  404. #           ifdef MIPS
  405. #             define HEAPSTART 0x10000000
  406. #             define HEAPLIM 0x20000000
  407. #           else
  408. #          ifdef IBMRS6000
  409. #        define HEAPSTART 0x80000000
  410. #        define HEAPLIM 0x8ff70000
  411. #          else
  412.              --> values unknown <--
  413. #          endif
  414. #           endif
  415. #         endif
  416. #       endif
  417. #     endif
  418. #   endif
  419. # endif
  420. #endif
  421.  
  422. /*********************************/
  423. /*                               */
  424. /* Machine-dependent defines     */
  425. /*                               */
  426. /*********************************/
  427.  
  428. #define WORDS_TO_BYTES(x)   ((x)<<2)
  429. #define BYTES_TO_WORDS(x)   ((x)>>2)
  430.  
  431. #define WORDSZ              32
  432. #define LOGWL               5    /* log[2] of above */
  433. #define BYTES_PER_WORD      (sizeof (word))
  434. #define modHALFWORDSZ(n) ((n) & 0xf)    /* mod n by size of half word    */
  435. #define divHALFWORDSZ(n) ((n) >> 4)    /* divide n by size of half word */
  436. #define modWORDSZ(n) ((n) & 0x1f)       /* mod n by size of word         */
  437. #define divWORDSZ(n) ((n) >> 5)         /* divide n by size of word      */
  438.  
  439. /*********************/
  440. /*                   */
  441. /*  Size Parameters  */
  442. /*                   */
  443. /*********************/
  444.  
  445. /*  heap block size, bytes */
  446. /* for RT see comment below */
  447.  
  448. #define HBLKSIZE   0x1000   /* Must be power of 2 */
  449.  
  450.  
  451. /*  max size objects supported by freelist (larger objects may be   */
  452. /*  allocated, but less efficiently)                                */
  453. /*      asm(".set MAXOBJSZ,0x200")      if HBLKSIZE/2 == 0x200      */
  454.  
  455. #define MAXOBJSZ    (HBLKSIZE/8)
  456.         /* Should be BYTES_TO_WORDS(HBLKSIZE/2), but a cpp */
  457.         /* misfeature prevents that.                       */
  458.  
  459. # define divHBLKSZ(n) ((n) >> 12)
  460.  
  461. # define modHBLKSZ(n) ((n) & (HBLKSIZE-1))
  462.  
  463. # define HBLKPTR(objptr) ((struct hblk *)(((long) (objptr)) & ~(HBLKSIZE-1)))
  464.  
  465.  
  466.  
  467. /********************************************/
  468. /*                                          */
  469. /*    H e a p   B l o c k s                 */
  470. /*                                          */
  471. /********************************************/
  472.  
  473. /*  heap block header */
  474. #define HBLKMASK   (HBLKSIZE-1)
  475.  
  476. #define BITS_PER_HBLK (HBLKSIZE * 8)
  477.  
  478. #define MARK_BITS_PER_HBLK (BITS_PER_HBLK/WORDSZ)
  479.        /* upper bound                                    */
  480.        /* We allocate 1 bit/word.  Only the first word   */
  481.        /* in each object is actually marked.             */
  482.  
  483. # ifdef ALIGN_DOUBLE                                            
  484. #   define MARK_BITS_SZ (((MARK_BITS_PER_HBLK + 2*WORDSZ - 1)/(2*WORDSZ))*2)
  485. # else                                          
  486. #   define MARK_BITS_SZ ((MARK_BITS_PER_HBLK + WORDSZ - 1)/WORDSZ)
  487. # endif
  488.        /* Upper bound on number of mark words per heap block  */
  489.  
  490. struct hblkhdr {
  491.     long hbh_sz;    /* sz > 0 ==> objects are sz-tuples of poss. pointers */
  492.             /* sz < 0 ==> objects are sz-tuples not pointers      */
  493.             /* if free, the size in bytes of the whole block      */
  494.             /* Misc.c knows that hbh_sz comes first.              */
  495.     struct hblk * hbh_next; /* Link field for hblk free list    */
  496.     struct hblk * hbh_sz_link;
  497.                 /* Next heap block containing objects of the */
  498.                 /* same size as this one, on which garbage   */
  499.                 /* objects have not yet been reclaimed.      */
  500.     char hbh_uninit;  /* If this is a free heap block, then it has not been */
  501.                   /* cleared.                       */                
  502.     char hbh_tenured;               /* This block should not be reclaimed  */
  503.                        /* because it contains too few empty   */
  504.                        /* objects.                 */
  505.                        /* Allocated blocks only.           */
  506.     unsigned char hbh_last_reclaimed;   /* gc_no when block was last       */
  507.                         /* reclaimed or reallocated.  Not  */
  508.                         /* valid for large object blocks.  */
  509.                         /* Used defensively, since it      */
  510.                         /* might wrap around.           */
  511.     char hbh_busy;        /* Currently being reclaimed.    */
  512.                     /* Valid only for allocated blocks. */
  513.     long hbh_marks[MARK_BITS_SZ];
  514.                 /* Bit i in the array refers to the             */
  515.                 /* object starting at the ith word (header      */
  516.                 /* INCLUDED) in the heap block.                 */
  517.                 /* For free blocks, hbh_marks[0] = 1, indicates */
  518.                 /* block is uninitialized.                      */
  519.                 /* For allocated blocks, hbh_marks[0] = 1       */
  520.                 /* indicates that the block should not be       */
  521.                 /* reclaimed during a partial collection.        */
  522.                 /* This should be changed if HBLKSIZE is        */
  523.                  /* decreased.                    */
  524. };
  525.  
  526. /*  heap block body */
  527.  
  528.  
  529. # ifdef SEPARATE_HEADERS
  530. #   ifdef UNALIGNED
  531. #     define BODY_SZ ((HBLKSIZE-WORDS_TO_BYTES(DISCARD_WORDS))/sizeof(word))
  532.       struct hblk {
  533.     word garbage[DISCARD_WORDS];
  534.     word hb_body[BODY_SZ];
  535.       };
  536. #     define HDR_BYTES WORDS_TO_BYTES(DISCARD_WORDS)
  537. #   else
  538. #     define BODY_SZ ((HBLKSIZE \
  539.                        -WORDS_TO_BYTES(ALIGNED_DISCARD_WORDS))/sizeof(word))
  540.       struct hblk {
  541. #       if ALIGNED_DISCARD_WORDS != 0
  542.       word garbage[ALIGNED_DISCARD_WORDS];
  543. #    endif
  544.     word hb_body[BODY_SZ];
  545.       };
  546. #     define HDR_BYTES WORDS_TO_BYTES(ALIGNED_DISCARD_WORDS)
  547. #   endif
  548. # else
  549. #   define BODY_SZ ((HBLKSIZE-sizeof(struct hblkhdr))/sizeof(word))
  550.     struct hblk {
  551.       struct hblkhdr hb_hdr;
  552.       word hb_body[BODY_SZ];
  553.     };
  554. #   define HDR_BYTES (sizeof (struct hblkhdr))
  555. # endif
  556.  
  557. # define HDR_WORDS BYTES_TO_WORDS(HDR_BYTES)
  558.  
  559. # ifdef SEPARATE_HEADERS
  560. #   define HDR(h) headers[divHBLKSZ((unsigned)(h) - (unsigned) GC_heapstart)]
  561. #   define hb_sz(h) (HDR(h) -> hbh_sz)
  562. #   define hb_sz_from_hdr(hhdr) (hhdr -> hbh_sz)
  563. #   define hb_marks(h) (HDR(h) -> hbh_marks)
  564. #   define hb_next(h) (HDR(h) -> hbh_next)
  565. #   define hb_sz_link(h) (HDR(h) -> hbh_sz_link)
  566. #   define hb_sz_link_from_hdr(hhdr) (hhdr -> hbh_sz_link)
  567. #   define hb_uninit(h) (HDR(h) -> hbh_uninit)
  568. #   define hb_tenured(h) (HDR(h) -> hbh_tenured)
  569. #   define hb_busy(h) (HDR(h) -> hbh_busy)
  570. #   define hb_busy_from_hdr(hhdr) (hhdr -> hbh_busy)
  571.     /* Cannot use mark bits, since they can accidentally get set if the */
  572.     /* block is in use.                                                 */
  573. #   define hb_last_reclaimed(h) (HDR(h) -> hbh_last_reclaimed)
  574. # else
  575. #   define hb_sz(h) ((h) -> hb_hdr.hbh_sz)
  576. #   define hb_marks(h) ((h) -> hb_hdr.hbh_marks)
  577. #   define hb_next(h) ((h) -> hb_hdr.hbh_next)
  578. #   define hb_sz_link(h) ((h) -> hb_hdr.hbh_sz_link)
  579. #   define hb_uninit(h) ((h) -> hb_hdr.hbh_uninit)
  580. #   define hb_tenured(h) ((h) -> hb_hdr.hbh_tenured)
  581. #   define hb_busy(h) ((h) -> hb_hdr.hbh_busy)
  582. #   define hb_last_reclaimed(h) ((h) -> hb_hdr.hbh_last_reclaimed)
  583. #   ifdef ALIGN_DOUBLE
  584. #       define hb_dummy(h) ((h) -> hb_hdr.hbh_dummy)
  585. #   endif
  586. # endif
  587.  
  588. # ifdef SEPARATE_HEADERS
  589.   /* Free list for heap block headers */
  590.   typedef struct hblkhdr hdr;
  591.  
  592. # define HDR_NIL ((hdr *)0)
  593.  
  594. # define link(h) ((hdr *)((h) -> hbh_sz))  /* Link field for free list */
  595.  
  596. # define set_link(h, p) (h) -> hbh_sz = (long)(p);
  597.  
  598. # endif
  599.  
  600.  
  601. /****************************/
  602. /*                          */
  603. /*   Objects                */
  604. /*                          */
  605. /****************************/
  606.  
  607. /*  object structure */
  608.  
  609. struct obj {
  610.     union {
  611.     word oun_link;   /* --> next object in freelist */
  612.              /* "encrypted" using macros    */
  613.              /* below.  This prevents a     */
  614.              /* false reference to a free   */
  615.              /* list from pinning the     */
  616.              /* entire list.        */
  617.     word oun_component[1];  /* treats obj as list of words */
  618. #         define obj_component  obj_un.oun_component
  619.     } obj_un;
  620. };
  621.  
  622. # define ENCRYPT_POINTER(p)  (~((word) (p)))
  623. # define DECRYPT_POINTER(p)  (struct obj *)(~(p))
  624. # define get_obj_link(p)   DECRYPT_POINTER((p) -> obj_un.oun_link)
  625. # define set_obj_link(p,q)  ((p) -> obj_un.oun_link = ENCRYPT_POINTER(q))
  626.  
  627. /*  Test whether something points to a legitimate heap object */
  628.  
  629. /* Check whether the given HBLKSIZE aligned hblk pointer refers to the   */
  630. /* beginning of a legitimate chunk.                                      */
  631. /* Assumes that *p is addressable                                        */
  632. # define is_hblk(p)  (hblkmap[divHBLKSZ(((long)p) - ((long)GC_heapstart))] \
  633.             == HBLK_VALID)
  634.             
  635. # ifdef INTERIOR_POINTERS
  636.   /* Return the hblk_map entry for the pointer p */
  637. #  define get_map(p) (hblkmap[divHBLKSZ(((long)p) - ((long)GC_heapstart))])
  638. # endif
  639.  
  640. # define WORD_NO(obj_ptr, hblk_ptr)  (((word *) obj_ptr) - ((word *) hblk_ptr))
  641.  
  642. # define IDIV(x,y) ((x)/(y))
  643.     /* Allows replacement with a faster implementation on a SPARC.    */
  644.     /* We no longer consider this worth the table size, since the    */
  645.     /* collector calls it rarely.                    */
  646.  
  647. /* Return the word displacement of the beginning of the object that    */
  648. /* includes the word displacement w.                            */
  649. /* Assumes sz <= MAXOBJSZ.                              */
  650. /* Second version assumes obj_map[sz] is not nil.                  */
  651. # define adjusted_word_no(w,sz) \
  652.           (IDIV((w - HDR_WORDS), (sz)) * (sz) + HDR_WORDS)
  653.           
  654. # ifdef INTERIOR_POINTERS
  655. #  define mapped_adjusted_word_no(w,sz) (w - obj_map[sz][w])
  656.         
  657. #   ifdef RESTRICTED_INTERIOR_POINTERS
  658.       /* Check whether w is a valid word offset into a heap block for */
  659.       /* objects of size sz.  Assumes sz < MAXOBJSZ and that w < size */
  660.       /* of one heap block, but > HDR_WORDS.                  */
  661.       /* May lie about pointers past the last object in the block.    */
  662. #     define is_proper_obj(w,sz) \
  663.           valid_offsets[(w - HDR_WORDS) % (sz)]
  664.       
  665. #   else
  666. #     define is_proper_obj(w,sz) 1
  667. #   endif        
  668. # else /* no interior pointers */
  669. #  define is_proper_obj(w,sz) \
  670.           ((w - HDR_WORDS) % (sz) == 0)
  671.         
  672. # endif
  673.  
  674. /* The following is a quick test whether something is an object pointer */
  675. /* It may err in the direction of identifying bogus pointers            */
  676. /* Assumes heap + text + data + bss < 256 Meg                    */
  677. #ifdef M68K_SUN
  678. #   define TMP_POINTER_MASK 0xf0000003  /* pointer & POINTER_MASK should be 0 */
  679. #else
  680. # ifdef RT
  681. #   define TMP_POINTER_MASK 0xc0000003
  682. # else
  683. #   ifdef VAX
  684. #     define TMP_POINTER_MASK 0xf0000003
  685. #   else
  686. #     ifdef SPARC
  687. #       define TMP_POINTER_MASK 0xf0000003
  688. #     else
  689. #       ifdef I386
  690. #         define TMP_POINTER_MASK 0xf0000003
  691. #       else
  692. #         ifdef NS32K
  693. #           define TMP_POINTER_MASK 0xf0000003
  694. #         else
  695. #           ifdef MIPS
  696. #             define TMP_POINTER_MASK 0xc0000003
  697. #           else
  698. #             ifdef M68K_HP
  699. #               define TMP_POINTER_MASK 0xf0000003
  700. #             else
  701. #        ifdef IBMRS6000
  702. #          define TMP_POINTER_MASK 0x70000003
  703. #        else
  704.               --> dont know <--
  705. #        endif
  706. #             endif
  707. #           endif
  708. #         endif
  709. #       endif
  710. #     endif
  711. #   endif
  712. # endif
  713. #endif
  714.  
  715. #ifdef INTERIOR_POINTERS
  716. #   define POINTER_MASK (TMP_POINTER_MASK & 0xfffffff8)
  717.     /* Don't pay attention to whether address is properly aligned */
  718. #else
  719. #   define POINTER_MASK TMP_POINTER_MASK
  720. #endif
  721.  
  722. #ifdef UNALIGNED
  723. #    define quicktest(p) (((long)(p)) > ((long)(GC_heapstart)) \
  724.               && !(((unsigned long)(p)) & POINTER_MASK) \
  725.               && (((long)(p)) & (HBLKMASK ^ 0x1f)))
  726. #else
  727. #  ifdef IBMRS6000
  728. #    define quicktest(p) (((unsigned long)(p)) \
  729.                           > ((unsigned long)(GC_heapstart)) \
  730.                           && !(((unsigned long)(p)) & POINTER_MASK))
  731. #   else
  732. #    define quicktest(p) (((long)(p)) > ((long)(GC_heapstart)) \
  733.               && !(((unsigned long)(p)) & POINTER_MASK))
  734. #   endif
  735. #endif
  736.  
  737.  
  738. /*  Marks are in a reserved area in each header.             */
  739. /*  Each word has one mark bits associated                   */
  740. /*  with it. Only those corresponding to the beginning of an */
  741. /*  object are used.                                         */
  742.  
  743.  
  744. /* Operations */
  745.  
  746. /*
  747.  * Retrieve, set, clear the mark bit corresponding
  748.  * to the nth word in a given heap block.
  749.  * Note that retrieval will work, so long as *hblk is addressable,
  750.  * or there is a legitimate header associated with h.
  751.  * In particular, the check whether hblk is a legitimate heap block
  752.  * can be postponed until after the mark bit is examined.
  753.  *
  754.  * (Recall that bit n corresponds to object beginning at word n)
  755.  */
  756.  
  757. # define mark_bit(hblk,n) ((hb_marks(hblk)[divWORDSZ(n)] \
  758.                 >> (modWORDSZ(n))) & 1)
  759.             
  760. # ifdef SEPARATE_HEADERS
  761. # define mark_bit_from_hdr(hblkhdr,n) (((hblkhdr) -> hbh_marks[divWORDSZ(n)] \
  762.                            >> (modWORDSZ(n))) & 1)
  763.  
  764. # endif            
  765.  
  766. /* The following assume the mark bit in question is either initially */
  767. /* cleared or it already has its final value                         */
  768. # define set_mark_bit(hblk,n) hb_marks(hblk)[divWORDSZ(n)] \
  769.                 |= 1 << modWORDSZ(n)
  770.                 
  771. # ifdef SEPARATE_HEADERS
  772. #   define set_mark_bit_from_hdr(hblkhdr,n) \
  773.            (hblkhdr) -> hbh_marks[divWORDSZ(n)] \
  774.     |= 1 << modWORDSZ(n)
  775. # endif
  776.  
  777. # define clear_mark_bit(hblk,n) hb_marks(hblk)[divWORDSZ(n)] \
  778.                 &= ~(1 << modWORDSZ(n))
  779.                 
  780. /* Data structure for list of uncollectable objects. */
  781. struct uncollectable_structure {
  782.   struct uncollectable_structure *next;
  783.   char *addr1;
  784.   char *addr2;
  785. };
  786.  
  787. /* List of data segments to be used as roots. */
  788. struct data_list {
  789.     char *start, *end;
  790. };
  791.                 
  792. /* Procedures private to the collector. */                
  793.  
  794. /* Small object allocation routines.  Ensure nonempty free list. */
  795. /* Take size (in words) as argument.                  */
  796.  
  797. bool GC_allocobj(/* unsigned size_in_words */);
  798. bool GC_allocaobj(/* unsigned size_in_words */);
  799.  
  800. /* Heap block allocation procedures */
  801.  
  802. extern void GC_freehblk(/* struct hblk * h */);
  803.  
  804. extern struct hblk * GC_allochblk(/* long signed_obj_size_in_words */);
  805.  
  806. void GC_add_hblklist(/* struct hblk * hbp*/);
  807.  
  808. void GC_del_hblklist(/* struct hblk * hbp*/);
  809.  
  810. /* Heap expansion: */
  811. struct hblk * GC_get_sys_mem(/* unsigned long size_in_bytes */);
  812.                       /* Get a page aligned block of memory. Assumes */
  813.                       /* we have the allocation monitor lock.           */
  814.                       /* returns (struct hblk *)0 on failure.           */
  815.                       
  816. struct hblk * GC_get_sys_mem_initial(/* unsigned long size_in_bytes */);
  817.             /* Similar to the above, but intended to be    */
  818.             /* called before the threads world starts up.   */
  819.                       
  820. bool GC_expand_hp(/* unsigned size_in_hblks, bool initial */);
  821.             /* Get more system memory and add it to heap.  */
  822.             /* Assumes we hold allocation lock.           */
  823.             /* Returns TRUE on success.               */
  824.             /* Initial ==> threads world hasn't started    */
  825.             /* yet.                           */
  826.  
  827. /* Utilities */
  828.  
  829. void GC_printf(/* char * fmt, ... */);
  830.  
  831. void GC_vprintf(/* char * fmt, ... */);  /* Print only at high verbosity */
  832.  
  833. void GC_iprintf(/* char * fmt, ... */);  /* Print important info */
  834.  
  835. void GC_abort(/* char * msg_without_nl */);
  836.  
  837. void GC_RunExclusive(/* void (*proc), XR_Pointer arg */);
  838.  
  839. void GC_RunParallel(/* XR_MesaProc mp */);
  840.  
  841. void GC_lock_to_fixed_vp();
  842.     /* myself to vp 0, so that the UNIX stack can be used.     */
  843.  
  844. unsigned long GC_check_faults();  /* Number of page faults so far. */
  845.  
  846. /* Heap block partitioning (alloc.c): */
  847.  
  848. bool GC_new_hblk(/* long signed_obj_size_in_words */);
  849.                  /* allocate block and build free list. */
  850.  
  851. /* Heap block header allocation: */
  852. # ifdef SEPARATE_HEADERS
  853. void GC_get_header(/* struct hblk *h */);
  854.     /* Make sure that a header is available for heap block h */
  855.     
  856. void GC_use_as_headers(/* word *h, long n*/);
  857.     /* Release the block at h of size n * HBLKSIZE for use as heap     */
  858.     /* block headers Must be called sufficiently frequently that we */
  859.     /* never run out.                                 */
  860.     
  861. # ifdef DIRTY_BITS
  862. void GC_unprotect_headers();
  863.     /* Unprotect all pages in memory that include only headers.   */
  864.     /* This interacts with ThreadsVirtualDirty.c.  It may safely  */
  865.     /* be called at any time, PROVIDED we do not care about dirty */
  866.     /* bit information on the headers.  Calling it may improve    */
  867.     /* performance.  Note however, that it only affects the       */
  868.     /* current virtual processor.                      */
  869.     /* This assumes that dirty bits are implemented by           */
  870.     /* protecting memory.                          */
  871. # endif DIRTY_BITS
  872. # endif SEPARATE_HEADERS
  873.  
  874. /* Garbage collection, as a whole: */
  875. /* The deamon runs in a sep thread and calls all of these routines. */
  876. void GC_daemon();       /* Check whether a garbage collection should    */
  877.             /* be started.  If so, start one of the          */
  878.             /* appropriate flavor.                  */
  879.                   
  880. void GC_full_collection(/* bool stop_the_world */); /* do a full collection */
  881. void GC_partial_collection();  /* do a partial collection */
  882. void GC_freeze_and_start_reclaim(); /* finish the mark and start the reclaim */
  883. void GC_mark_with_constant_stack(/* int flags */);
  884.                                   /* nail the process to a stack and do */
  885.                                   /* some marking.  */
  886. void GC_mark_with_constant_stack_inner(/*  XR_Pointer clientData */);
  887.                                  /* internal routine for above */
  888. void GC_parallel_mark(); /* run the partial parallel marker */
  889. XR_Pointer GC_Partial_Mark_Inner(/* XR_MesaProc self */);
  890. void GC_full_parallel_mark(); /* run the full marker */
  891. XR_Pointer GC_Full_Mark_Inner(/*XR_MesaProc self*/);
  892. void GC_exclusive_mark();         /* Garbage collect, assuming we */
  893.                      /* own the allocation monitor   */
  894.                      /* lock.             */
  895. void GC_exclusive_mark_inner();
  896. void GC_collector_setup();
  897.  
  898. void GC_heap_full();    /* Invoke whatever collection is appropriate    */
  899.             /* for having run out of small object heap      */
  900.             /* spave.                    */
  901.             
  902. void GC_reclaim_hblks(/* long lw */);
  903.             /* Analogous to GC_heap_full, but we need a       */
  904.             /* space for a large object of size lw words.   */
  905.  
  906. /* Garbage collector mark phase: */
  907. XR_Pointer GC_Mark_and_GCollect_Proc(/* int flags */);
  908.               /* Mark and the invoke collector, adjusting priorities */
  909.               /* appropriately.  Return 0.                   */
  910.               
  911. XR_Pointer GC_Mark_Proc(/* int flags */);
  912.               /* Concurrently remark, adjusting priorities */
  913.               /* appropriately.  Return 0.             */
  914.               
  915. void GC_partial_parallel_gc();
  916.          /* start up a thread to mark and to perform a partial    */
  917.          /* collection.                        */
  918.          
  919. void GC_full_parallel_mark();
  920.         /* Start a process that reclaims all pages that were      */
  921.         /* reclaimed in the last cycle, flushes the rest, clears  */
  922.         /* all mark bits, and remarks from scratch.          */
  923.         /* Return when the process completes.              */
  924.         
  925. void GC_wait_for_gc();    
  926.         /* Wait until the current parallel collection is done.  */
  927.         /* Requires GC_allocate_ml.                */
  928.  
  929. void GC_mark_rescuers();
  930.  
  931. void GC_mark_roots(/* int mark_clean*/);
  932.             /* Push all (or dirty) roots onto the mark stack. */
  933.             /* See GC_mark_all for mark_clean values.      */
  934.  
  935. void GC_mark(/* int alignment */);  /* Mark everything on the mark stack */
  936.  
  937. void GC_clear_marks();   /* Clear all mark bits */
  938.  
  939. void GC_mark_all( /* word * b, word * t, int alignment, bool mark_clean */ );
  940. # define POSSIBLY_DIRTY_POINTERS 2
  941. # define DEFINITELY_DIRTY_POINTERS 3
  942. # define ALL_POINTERS 4
  943.         /* Push all pointers between b and t onto the mark stack   */
  944.         /* If mark_clean is POSSIBLY_DIRTY_ROOTS, ignore clean     */
  945.         /* pages when convenient. If it is DEFINITELY_DIRTY_ROOTS  */
  946.         /* also ignore pages without dirty bits.           */
  947. void GC_tl_mark(/* word * ptr */);  /* Add ptr to the mark stack.  (Slow.) */
  948.  
  949. void GC_tl_mark_all(/* word * b, word * t */);
  950.             /* Similar ot GC_mark_all, but uses ALIGNMENT value */
  951.             /* defined here.                    */
  952.             
  953. bool GC_tl_mark_all_but_gc(/* word *b , word * t */);
  954.         /* Similar to the above, but excl. GC area. Returns TRUE */
  955.  
  956. /* Garbage collector sweep phase: */
  957.  
  958. bool GC_hblk_empty(/* struct hblk *hbp */);
  959.             /* Is a block empty? May err on no side. */
  960.  
  961. void GC_reclaim_entire_block(/* struct hblk *hbp */);
  962.             /* Make entire block allocatable again. */
  963.  
  964. bool GC_hblk_probably_tenurable();
  965.  
  966. bool GC_hblk_definitely_tenurable();
  967.  
  968. void GC_reclaim_composite();
  969.  
  970. void GC_reclaim_atomic();
  971.  
  972. void GC_flush_reclaim_pages();
  973.  
  974. void GC_reclaim();
  975.  
  976. /* Virtual dirty bits: */
  977.  
  978. void GC_clear_dirty_bits();
  979. void GC_clear_some_dirty_bits(/* char * start, char * limit */);
  980. void GC_get_dirty_bits();
  981. void GC_set_dirty_bits();
  982. void GC_propagate_dirty_bits();
  983.  
  984. /* Heap block map cache: */
  985.  
  986. void GC_flush_map_cache();
  987.  
  988. void GC_add_cache_entry();
  989.  
  990. /* Finalization: */
  991.  
  992. void GC_TraceFinalizableObjects();
  993.  
  994. /* Collector variables declared as globals, but intended to be private to */
  995. /* the collector.                              */
  996. /* These are declared in  and initialized in globals.c,                */
  997. /* to ensure that they all end up in the data segment, adjacent to     */
  998. /* each other.                                   */
  999.  
  1000. extern char end;    /* Used to find end of bss segment.  Not included in */
  1001.             /* globals.c.                         */
  1002.  
  1003. extern word GC_first_global;
  1004.  
  1005. extern unsigned GC_mode;  /* Type of garbage collections to be performed. */
  1006. extern unsigned GC_requested_mode;  /* Mode to switch to at next    */
  1007.                     /* opportunity.            */
  1008. # define DIRTY_BITS_REQUIRED (GC_INCREMENTAL | GC_PARALLEL)
  1009.  
  1010.  
  1011. extern struct hblk * GC_hblkfreelist;  /* list of free heap blocks. */
  1012.  
  1013. # ifdef PRINTSTATS
  1014.     long GC_reclaim_count;     /* Number of reclaimed small object blocks */
  1015. # endif
  1016.  
  1017. /*
  1018.  * Private versions of various GC statistics variables.  These are cleared
  1019.  * when mark bits are cleared.  Thus, unlike the public versions, they do
  1020.  * not contain plausible values during a parallel full collection.
  1021.  */
  1022. extern long GC_my_composite_in_use;
  1023. extern long GC_my_atomic_in_use;
  1024. extern long GC_my_objects_in_use;
  1025.  
  1026. extern bool GC_demand_collection;    /* Set when there's an asynch request */
  1027.  
  1028. # ifdef SEPARATE_HEADERS
  1029.   /* Free list for heap block headers */
  1030.   extern hdr * GC_hdr_fl;
  1031. # endif
  1032.  
  1033. /* Monitor locks for allocation, and allocator callback respectively */
  1034. extern struct XR_MLRep GC_allocate_ml;
  1035.      /* Protects free list and reclaim list data structures, as well as */
  1036.      /* GC_collection_in_progress variable.                  */
  1037.      /* Mark bits are valid only      */
  1038.      /* for pages which reside on a reclaim list.  They may be set      */
  1039.      /* asynchronously on pages being reclaimed, but only if they are   */
  1040.      /* valid before and after the bit was set; this can only happen    */
  1041.      /* as a consequence of a misidentified pointer.            */
  1042. extern struct XR_MLRep GC_alloc_callback_ml;
  1043.  
  1044. /* Finalization Queue: */
  1045. # ifdef FINALIZE
  1046.   extern XR_FinalizationHandle GC_finalizeListHead;
  1047. # endif /* FINALIZE */
  1048.  
  1049.  
  1050. /* Garbage collector callbacks: */
  1051. extern RegisterGCCallbackType GC_callBackBefore, GC_callBackAfter,
  1052.                   GC_callBackDuring;
  1053. extern XR_Pointer GC_callBackBeforeClientData, GC_callBackAfterClientData,
  1054.           GC_callBackDuringClientData;
  1055.  
  1056. /* Mark stack.  We assume that we can use the UNIX stack for this purpose. */
  1057. /* All items between GC_mark_stack_top+1 and GC_mark_stack_bottom still    */
  1058. /* need to be marked.  All values on the stack are assumed to have passed  */
  1059. /* quicktest, but are not guaranteed to be valid object pointers.       */
  1060. /* Since we assume that we have the UNIX stack all to ourselves,        */
  1061. /* GC_mark_stack_bottom is set exactly once on startup.               */
  1062. word * GC_mark_stack_bottom;
  1063. extern word * GC_mark_stack_top;
  1064. # define STACKGAP 2048 /* Gap in longwords between hardware stack and    */
  1065.                /* the mark stack.                */
  1066.                /* Must suffice for printf calls and signal      */
  1067.                /* handling.                    */
  1068. # define PUSH_MS(ptr) *(--GC_mark_stack_top) = (word) ptr
  1069. # define USE_STACK  /* Some code also allows a heap resident mark stack. */
  1070.  
  1071. /* List of root segments for marking: */
  1072. extern long GC_num_data;   /* Number of entries in GC_data_list */
  1073.  
  1074. # define MAX_DATA_LIST 1000
  1075.  
  1076. extern struct data_list GC_data_list[MAX_DATA_LIST];
  1077.                     /* List of all data areas that must be treated as roots */
  1078.                     /* by the collector.                    */
  1079.  
  1080. /*  lists of all heap blocks and free lists  */
  1081.  
  1082. struct obj * GC_aobjfreelist[MAXOBJSZ+1];  /* atomic object free list headers */
  1083. struct obj * GC_objfreelist[MAXOBJSZ+1];   /* composite object ...            */
  1084.     /* Note that the headers conatin unencrypted pointers.  Links are   */
  1085.     /* "encrypted" with ENCRYPT_POINTER.                */                            
  1086.  
  1087. char GC_hblkmap[MAP_SIZE]; /* Indexed by offset from GC_heapstart       */
  1088.                /* Identifies which blocks are administered  */
  1089.                /* by collector.                             */
  1090. # define HBLK_INVALID 0    /* Not administered by collector   */
  1091. # define HBLK_VALID 0x7f   /* Beginning of a valid heap block */
  1092.     /* A value n, 0 < n < 0x7f denotes the continuation of a valid heap    */
  1093.     /* block which starts at the current address - n * HBLKSIZE or earlier */
  1094.     
  1095. # ifdef BLACK_LIST
  1096.     char GC_blacklist[MAP_SIZE];    /* Nonzero ==> false reference */
  1097. #   define black_list(hbp) \
  1098.         GC_blacklist[divHBLKSZ(((long)(hbp)) - ((long) GC_heapstart))]
  1099.         /* This keeps some of Sun's compilers from calling .div */
  1100. #   define is_black_listed(hbp) (black_list(hbp) != 0)
  1101. # endif
  1102.  
  1103. struct hblk * GC_reclaim_list[MAXOBJSZ+1];  /* Heap blocks of a given size */
  1104.                         /* waiting for reclamation     */
  1105. struct hblk * GC_areclaim_list[MAXOBJSZ+1];  /* Again, for atomic objects */
  1106.  
  1107. unsigned long GC_reclaim_inval_counter;    /* Incremented whenever reclaim    */
  1108.                     /* lists or mark bits are     */
  1109.                     /* invalidated.  Reclaim    */
  1110.                     /* procedures discard results   */
  1111.                     /* if this changed.        */
  1112.                     /* Protected by GC_allocate_ml. */
  1113. char * GC_obj_map[MAXOBJSZ+1];
  1114.                        /* If not NIL, then a pointer to a map of valid  */
  1115.                    /* object addresses. hbh_map[sz][i] is j if the  */
  1116.                    /* address block_start+4*i is a valid pointer    */
  1117.                    /* to an object at block_start+4*(i-j).  It is   */
  1118.                    /* OBJ_INVALID if block_start+4*i is not valid   */
  1119.                    /* as a pointer to an object.                */
  1120.                    /* We assume that all values of j <= OBJ_INVALID */
  1121.                    /* Note that this is effectively a mapping on    */
  1122.                    /* longword addresses; low order bits must       */
  1123.                    /* be masked off before it can be applied.       */
  1124. #       define OBJ_INVALID  0x7f                  
  1125.     
  1126.  
  1127. # ifdef RESTRICTED_INTERIOR_POINTERS
  1128.       char GC_valid_offsets[MAX_OFFSET+1]; 
  1129.               /* valid_offsets[i] != 0 iff i is a valid byte offset */
  1130.               /* of a pointer from the beginning of the object.     */
  1131. # endif   
  1132.    
  1133. # ifdef SEPARATE_HEADERS
  1134.     struct hblkhdr * GC_headers[MAP_SIZE];
  1135.             /* Headers for heap blocks administered by collector */
  1136.             /* Invalid for blocks not administered by collector. */
  1137.             /* Indexed in the same manner as hblkmap.            */
  1138. # endif
  1139.  
  1140. char GC_map_cache[MAP_CACHE_SZ][HBLKSIZE/BYTES_PER_WORD];
  1141.                      /* Space used to hold GC_obj_map maps */ 
  1142.  
  1143. # ifdef MERGE_SIZES                     
  1144.     long GC_size_map[MAXOBJSZ+1];   /* Size i allocation requests are rounded */
  1145.                     /* up to size GC_size_map[i].          */
  1146. # endif
  1147.  
  1148. extern char GC_dirty_bits[/* MAP_SIZE + slop for data segment */];
  1149.                         /* != 0 ==> block may have been changed */
  1150.                         /* since the last time the entry was    */
  1151.                         /* cleared using one of the routines in */
  1152.                         /* dirty.c.                    */
  1153. extern char * VD_base;       /* Lowest address represented in the    */
  1154.                     /* above array. Always HBLKSIZE aligned */
  1155.  
  1156. word GC_last_global;
  1157.  
  1158. # define objfreelist GC_objfreelist
  1159. # define aobjfreelist GC_aobjfreelist
  1160. # define reclaim_list GC_reclaim_list
  1161. # define areclaim_list GC_areclaim_list
  1162. # define hblkmap GC_hblkmap
  1163. # define obj_map GC_obj_map
  1164. # define map_cache GC_map_cache
  1165. # ifdef RESTRICTED_INTERIOR_POINTERS
  1166. #   define valid_offsets GC_valid_offsets
  1167. # endif
  1168.  
  1169. # ifdef SEPARATE_HEADERS
  1170. #   define headers GC_headers
  1171. # endif
  1172.  
  1173. # define begin_gc_arrays ((char *)(&GC_first_global))
  1174. # define end_gc_arrays ((char *)(&GC_last_global))
  1175. # define HB_SIZE(p) abs(hb_sz(p))
  1176. # define abs(x)  ((x) < 0? (-(x)) : (x))
  1177.  
  1178. struct uncollectable_structure * GC_pin_head;
  1179.                     /* Head of list of uncollectable objects. */    
  1180.  
  1181. # endif
  1182.